﻿<!DOCTYPE html>
<html>
<head>
  <title>Virtualized Tree with TreeLayout</title>
  <!-- Copyright 1998-2021 by Northwoods Software Corporation. -->
  <meta name="description" content="An example of virtualization where a virtualized TreeLayout sets the bounds for each node data." />
  <meta name="viewport" content="width=device-width, initial-scale=1">

  <script src="../release/go.js"></script>
  <script src="../assets/js/goSamples.js"></script>  <!-- this is only for the GoJS Samples framework -->
  <script id="code">
    // this controls whether the tree grows deeper towards the right or downwards:
    var HORIZONTAL = true;

    function init() {
      if (window.goSamples) goSamples();  // init for these samples -- you don't need to call this
      var $ = go.GraphObject.make;  // for conciseness in defining templates

      // The Diagram just shows what should be visible in the viewport.
      // Its model does NOT include node data for the whole graph, but only that
      // which might be visible in the viewport.
      myDiagram =
        $(go.Diagram, "myDiagramDiv",
          {
            initialDocumentSpot: go.Spot.Center,
            initialViewportSpot: go.Spot.Center,

            // Use a virtualized TreeLayout which does not require
            // that the Nodes and Links exist first for an accurate layout
            layout:
              $(VirtualizedTreeLayout,
                { angle: (HORIZONTAL ? 0 : 90), nodeSpacing: 10 }),

            // Define the template for Nodes, used by virtualization.
            nodeTemplate:
              $(go.Node, "Auto",
                { isLayoutPositioned: false },  // optimization
                new go.Binding("position", "bounds", function(b) { return b.position; })
                  .makeTwoWay(function(p, d) { return new go.Rect(p.x, p.y, d.bounds.width, d.bounds.height); }),
                { width: 70, height: 20 },  // in cooperation with the load function, below
                $(go.Shape, "Rectangle",
                  new go.Binding("fill", "color")),
                $(go.TextBlock,
                  { margin: 2 },
                  new go.Binding("text", "color")),
                {
                  toolTip:
                    $("ToolTip",
                      $(go.TextBlock, { margin: 3 },
                        new go.Binding("text", "",
                          function(d) { return "key: " + d.key + "\nbounds: " + d.bounds.toString(); }))
                    )
                }
              ),

            // Define the template for Links
            linkTemplate:
              $(go.Link,
                {
                  fromSpot: (HORIZONTAL ? go.Spot.Right : go.Spot.Bottom),
                  toSpot: (HORIZONTAL ? go.Spot.Left : go.Spot.Top)
                },
                $(go.Shape)
              ),

            "SelectionMoved": function(e) {
              e.subject.each(function(n) {
                if (n instanceof go.Node) n.data.points = undefined;
              })
            },

            "animationManager.isEnabled": false
          });

      // This model includes all of the data
      myWholeModel =
        $(go.TreeModel);  // must match the model used by the Diagram, below

      // The virtualized layout works on the full model, not on the Diagram Nodes and Links
      myDiagram.layout.model = myWholeModel;

      // Do not set myDiagram.model = myWholeModel -- that would create a zillion Nodes and Links!
      // In the future Diagram may have built-in support for virtualization.
      // For now, we have to implement virtualization ourselves by having the Diagram's model
      // be different than the "real" model.
      myDiagram.model =   // this only holds nodes that should be in the viewport
        $(go.TreeModel);  // must match the model, above

      // for now, we have to implement virtualization ourselves
      myDiagram.isVirtualized = true;
      myDiagram.addDiagramListener("ViewportBoundsChanged", onViewportChanged);

      myDiagram.delayInitialization(function() { spinDuring("mySpinner", load); });
    }

    // implement a wait spinner in HTML with CSS animation
    function spinDuring(spinner, compute) {  // where compute is a function of zero args
      // show the animated spinner
      if (typeof spinner === "string") spinner = document.getElementById(spinner);
      if (spinner) {
        // position it in the middle of the viewport DIV
        var x = Math.floor(myDiagram.div.offsetWidth/2 - spinner.naturalWidth/2);
        var y = Math.floor(myDiagram.div.offsetHeight/2 - spinner.naturalHeight/2);
        spinner.style.left = x + "px";
        spinner.style.top = y + "px";
        spinner.style.display = "inline";
      }
      setTimeout(function() {
        try {
          compute();  // do the computation
        } finally {
          if (spinner) spinner.style.display = "none";
        }
      }, 20);
    }

    function load() {
      // create a lot of data for the myWholeModel
      var total = 123456;
      var treedata = [];
      for (var i = 0; i < total; i++) {
        var d = {
          key: i,  // this node data's key
          color: go.Brush.randomColor(),  // the node's color
          parent: (i > 0 ? Math.floor(Math.random() * i / 2) : undefined)  // the random parent's key
        };
        //!!!???@@@ this needs to be customized to account for your chosen Node template
        d.bounds = new go.Rect(0, 0, 70, 20);
        treedata.push(d);
      }
      myWholeModel.nodeDataArray = treedata;
      myDiagram.layoutDiagram(true);
    }


    // The following functions implement virtualization of the Diagram
    // Assume data.bounds is a Rect of the area occupied by the Node in document coordinates.

    // The normal mechanism for determining the size of the document depends on all of the
    // Nodes and Links existing, so we need to use a function that depends only on the model data.
    function computeDocumentBounds() {
      var b = new go.Rect();
      var ndata = myWholeModel.nodeDataArray;
      for (var i = 0; i < ndata.length; i++) {
        var d = ndata[i];
        if (!d.bounds) continue;
        if (i === 0) {
          b.set(d.bounds);
        } else {
          b.unionRect(d.bounds);
        }
      }
      return b;
    }

    // As the user scrolls or zooms, make sure the Parts (Nodes and Links) exist in the viewport.
    function onViewportChanged(e) {
      var diagram = e.diagram;
      // make sure there are Nodes for each node data that is in the viewport
      // or that is connected to such a Node
      var viewb = diagram.viewportBounds;  // the new viewportBounds
      var model = diagram.model;

      var oldskips = diagram.skipsUndoManager;
      diagram.skipsUndoManager = true;

      var b = new go.Rect();
      var ndata = myWholeModel.nodeDataArray;
      for (var i = 0; i < ndata.length; i++) {
        var n = ndata[i];
        if (model.containsNodeData(n)) continue;
        if (!n.bounds) continue;
        if (n.bounds.intersectsRect(viewb)) {
          model.addNodeData(n);
        }
        if (model instanceof go.TreeModel) {
          // make sure links to all parent nodes appear
          var parentkey = myWholeModel.getParentKeyForNodeData(n);
          var parent = myWholeModel.findNodeDataForKey(parentkey);
          if (parent !== null) {
            if (n.bounds.intersectsRect(viewb)) {  // N is inside viewport
              model.addNodeData(parent);  // so that link to parent appears
              var child = diagram.findNodeForData(n);
              if (child !== null) {
                var link = child.findTreeParentLink();
                if (link !== null) {
                  // do this now to avoid delayed routing outside of transaction
                  link.fromNode.ensureBounds();
                  link.toNode.ensureBounds();
                  if (child.data.fromSpot) link.fromSpot = child.data.fromSpot;
                  if (child.data.toSpot) link.toSpot = child.data.toSpot;
                  if (child.data.points) {
                    link.points = child.data.points;
                  } else {
                    link.updateRoute();
                  }
                }
              }
            } else {  // N is outside of viewport
              // see if there's a parent that is in the viewport,
              // or if the link might cross over the viewport
              b.set(n.bounds);
              b.unionRect(parent.bounds);
              if (b.intersectsRect(viewb)) {
                model.addNodeData(n);  // add N so that link to parent appears
                var child = diagram.findNodeForData(n);
                if (child !== null) {
                  var link = child.findTreeParentLink();
                  if (link !== null) {
                    // do this now to avoid delayed routing outside of transaction
                    link.fromNode.ensureBounds();
                    link.toNode.ensureBounds();
                    if (child.data.fromSpot) link.fromSpot = child.data.fromSpot;
                    if (child.data.toSpot) link.toSpot = child.data.toSpot;
                    if (child.data.points) {
                      link.points = child.data.points;
                    } else {
                      link.updateRoute();
                    }
                  }
                }
              }
            }
          }
        }
      }

      if (model instanceof go.GraphLinksModel) {
        var ldata = myWholeModel.linkDataArray;
        for (var i = 0; i < ldata.length; i++) {
          var l = ldata[i];
          var fromkey = myWholeModel.getFromKeyForLinkData(l);
          if (fromkey === undefined) continue;
          var from = myWholeModel.findNodeDataForKey(fromkey);
          if (from === null || !from.bounds) continue;

          var tokey = myWholeModel.getToKeyForLinkData(l);
          if (tokey === undefined) continue;
          var to = myWholeModel.findNodeDataForKey(tokey);
          if (to === null || !to.bounds) continue;

          b.set(from.bounds);
          b.unionRect(to.bounds);
          if (b.intersectsRect(viewb)) {
            // also make sure both connected nodes are present,
            // so that link routing is authentic
            model.addNodeData(from);
            model.addNodeData(to);
            model.addLinkData(l);
            var link = diagram.findLinkForData(l);
            if (link !== null) {
              // do this now to avoid delayed routing outside of transaction
              link.fromNode.ensureBounds();
              link.toNode.ensureBounds();
              if (link.data.fromSpot) link.fromSpot = link.data.fromSpot;
              if (link.data.toSpot) link.toSpot = link.data.toSpot;
              //if (link.data.points) {
              //  link.points = link.data.points;
              //} else {
                link.updateRoute();
              //}
            }
          }
        }
      }

      diagram.skipsUndoManager = oldskips;

      if (myRemoveTimer === null) {
        // only remove offscreen nodes after a delay
        myRemoveTimer = setTimeout(function() { removeOffscreen(diagram); }, 3000);
      }

      updateCounts();  // only for this sample
    }

    // occasionally remove Parts that are offscreen from the Diagram
    var myRemoveTimer = null;

    function removeOffscreen(diagram) {
      myRemoveTimer = null;

      var viewb = diagram.viewportBounds;
      var model = diagram.model;
      var remove = [];  // collect for later removal
      var removeLinks = new go.Set();  // links connected to a node data to remove
      var it = diagram.nodes;
      while (it.next()) {
        var n = it.value;
        var d = n.data;
        if (d === null) continue;
        if (!n.actualBounds.intersectsRect(viewb) && !n.isSelected) {
          // even if the node is out of the viewport, keep it if it is selected or
          // if any link connecting with the node is still in the viewport
          if (!n.linksConnected.any(function(l) { return l.actualBounds.intersectsRect(viewb); })) {
            remove.push(d);
            if (model instanceof go.GraphLinksModel) {
              removeLinks.addAll(n.linksConnected);
            }
          }
        }
      }

      if (remove.length > 0) {
        var oldskips = diagram.skipsUndoManager;
        diagram.skipsUndoManager = true;
        model.removeNodeDataCollection(remove);
        if (model instanceof go.GraphLinksModel) {
          removeLinks.each(function(l) { if (!l.isSelected) model.removeLinkData(l.data); });
        }
        diagram.skipsUndoManager = oldskips;
      }

      updateCounts();  // only for this sample
    }
    // end of virtualized Diagram


    // start of VirtualizedTree[Layout/Network] classes

    // Here we try to replace the dependence of TreeLayout on Nodes
    // with depending only on the data in the TreeModel.
    function VirtualizedTreeLayout() {
      go.TreeLayout.call(this);
      this.isOngoing = false;
      this.model = null;  // add this property for holding the whole TreeModel
    }
    go.Diagram.inherit(VirtualizedTreeLayout, go.TreeLayout);

    VirtualizedTreeLayout.prototype.createNetwork = function() {
      return new VirtualizedTreeNetwork(this);  // defined below
    };

    // ignore the argument, an (implicit) collection of Parts
    VirtualizedTreeLayout.prototype.makeNetwork = function(coll) {
      var net = this.createNetwork();
      net.addData(this.model);  // use the model data, not any actual Nodes and Links
      return net;
    };

    VirtualizedTreeLayout.prototype.commitLayout = function() {
      VirtualizedTreeEdge._dummyLink = this.diagram.linkTemplate.copy();
      VirtualizedTreeEdge._dummyFromNode = this.diagram.nodeTemplate.copy();
      VirtualizedTreeEdge._dummyToNode = this.diagram.nodeTemplate.copy();
      VirtualizedTreeEdge._dummyLink.fromNode = VirtualizedTreeEdge._dummyFromNode;
      VirtualizedTreeEdge._dummyLink.toNode = VirtualizedTreeEdge._dummyToNode;
      this.diagram.add(VirtualizedTreeEdge._dummyFromNode);
      this.diagram.add(VirtualizedTreeEdge._dummyToNode);
      this.diagram.add(VirtualizedTreeEdge._dummyLink);

      go.TreeLayout.prototype.commitLayout.call(this);
      // can't depend on regular bounds computation that depends on all Nodes existing
      this.diagram.fixedBounds = computeDocumentBounds();
      // update the positions of any existing Nodes
      this.diagram.nodes.each(function(node) {
        node.updateTargetBindings();
      });

      this.diagram.remove(VirtualizedTreeEdge._dummyFromNode);
      this.diagram.remove(VirtualizedTreeEdge._dummyToNode);
      this.diagram.remove(VirtualizedTreeEdge._dummyLink);
    };

    VirtualizedTreeLayout._cachedLinks = [];

    VirtualizedTreeLayout.prototype.setPortSpots = function(v) {
      v.destinationEdges.each(function(e) {
        e.link = VirtualizedTreeLayout._cachedLinks.pop() || new go.Link();
      });
      go.TreeLayout.prototype.setPortSpots.call(this, v);
      v.destinationEdges.each(function(e) {
        if (e.data) {
          e.data.fromSpot = e.link.fromSpot.copy();
          e.data.toSpot = e.link.toSpot.copy();
        }
        VirtualizedTreeLayout._cachedLinks.push(e.link);
        e.link = null;
      });
    }
    // end VirtualizedTreeLayout class


    function VirtualizedTreeNetwork(layout) {
      go.TreeNetwork.call(this, layout);
    }
    go.Diagram.inherit(VirtualizedTreeNetwork, go.TreeNetwork);

    VirtualizedTreeNetwork.prototype.createEdge = function() { return new VirtualizedTreeEdge(this); }

    VirtualizedTreeNetwork.prototype.addData = function(model) {
      if (model instanceof go.TreeModel) {
        var dataVertexMap = new go.Map();
        var ndata = model.nodeDataArray;
        for (var i = 0; i < ndata.length; i++) {
          var d = ndata[i];
          var v = this.createVertex();
          v.data = d;  // associate this Vertex with data, not a Node
          dataVertexMap.set(d, v);
          this.addVertex(v);
        }

        for (var i = 0; i < ndata.length; i++) {
          var child = ndata[i];
          var parentkey = model.getParentKeyForNodeData(child);
          var parent = model.findNodeDataForKey(parentkey);
          if (parent !== null) {  // if there is a parent, there should be an edge
            // now find corresponding vertexes
            var f = dataVertexMap.get(parent);
            var t = dataVertexMap.get(child);
            if (f === null || t === null) continue;  // skip
            // create and add VirtualizedTreeEdge
            var e = this.createEdge();
            e.data = child;  // associate this Edge with data, not a Link
            e.fromVertex = f;
            e.toVertex = t;
            this.addEdge(e);
          }
        }
      } else {
        throw new Error("can only handle TreeModel data");
      }
    };
    // end VirtualizedTreeNetwork class

    function VirtualizedTreeEdge(network) {
      go.TreeEdge.call(this, network);
    }
    go.Diagram.inherit(VirtualizedTreeEdge, go.TreeEdge);

    VirtualizedTreeEdge._dummyLink = null;
    VirtualizedTreeEdge._dummyFromNode = null;
    VirtualizedTreeEdge._dummyToNode = null;

    VirtualizedTreeEdge.prototype.commit = function() {
      var parentv = this.fromVertex;
      if (!parentv) return;
      var routed = (parentv.alignment === go.TreeLayout.AlignmentStart || parentv.alignment === go.TreeLayout.AlignmentEnd);
      if (this.data && routed) {
        this.link = VirtualizedTreeEdge._dummyLink;
        this.link.fromNode.position = new go.Point(this.fromVertex.x, this.fromVertex.y);
        this.link.toNode.position = new go.Point(this.toVertex.x, this.toVertex.y);
        this.link.fromNode.ensureBounds();
        this.link.toNode.ensureBounds();
        this.link.updateRoute();
      }
      go.TreeEdge.prototype.commit.call(this);
      if (this.data && routed) {
        this.data.points = this.link.points.copy();
        this.link = null;
      }
    }

    // end of VirtualizedTree[Layout/Network] classes

    // This function is only used in this sample to demonstrate the effects of the virtualization.
    // In a real application you would delete this function and all calls to it.
    function updateCounts() {
      document.getElementById("myMessage1").textContent = myWholeModel.nodeDataArray.length;
      document.getElementById("myMessage2").textContent = myDiagram.nodes.count;
      document.getElementById("myMessage4").textContent = myDiagram.links.count;
    }
  </script>
  <style>
    #mySpinner { display: none; position: absolute; z-index: 100; animation: spin 1s linear infinite; }
    @keyframes spin { from { transform: rotate(0deg); } to { transform: rotate(360deg); } }
  </style>
</head>
<body onload="init()">
<div id="sample">
  <div id="myDiagramDiv" style="background-color: white; border: solid 1px black; width: 100%; height: 600px"></div>
  <img id="mySpinner" src="images/spinner.png">
  <div id="description">
  <p>This uses a <a>TreeModel</a> and a virtualized <a>TreeLayout</a>.</p>
  Node data in Model: <span id="myMessage1"></span>.
  Actual Nodes in Diagram: <span id="myMessage2"></span>.
  Actual Links in Diagram: <span id="myMessage4"></span>.
  </div>
</div>
</body>
</html>
